package 平衡二叉树;
//题目描述
//输入一棵二叉树，判断该二叉树是否是平衡二叉树。
//
//在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
public class Solution
{
    //平衡二叉树的定义：
    //左右子树的高度之差不超过1
    //左右子树也是平衡二叉树
    public boolean IsBalanced_Solution(TreeNode root)
    {
        //从上到下递归遍历，会有相当多的重复
        //更好的方法是从下到上遍历
        return GetDepth(root)!=-1;
    }
    public int GetDepth(TreeNode root)
    {
        if (root==null)
            return 0;
        int left=GetDepth(root.left);
        if (left==-1)
            return -1;//发现一个子树不平衡，那么这棵树一定不平衡，不必进行后面的步骤
        int right=GetDepth(root.right);
        if (right==-1)
            return -1;
        if (Math.abs(left-right)>1)
            return -1;
        else
            return 1+(left>right?left:right);
    }
}
